package wangmin.common.region;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by wm on 2017/3/31. 平台区域变更, 将变更推送到所有依赖的 所有节点深度一致
 */
public abstract class RegionDifferenceForward {
	/**
	 * @param pre 原来的
	 * @param now 更新后的
	 * @param derivedFromPre 衍生自pre的
	 **/
	public static void transformOne(List<Region> pre, List<Region> now, List<Region> derivedFromPre) {
		assert (pre != null);
		assert (now != null);
		assert (derivedFromPre != null);
		cutDerivedToSubRegion(now, derivedFromPre);
		List<Region> added = new ArrayList<>();
		generateAddedRegion(pre, now, added);
		addRegion(added, derivedFromPre);
	}
	/**
	 * @param pre 原来的
	 * @param now 更新后的
	 * @param derivedFromPreList 衍生自pre的一组区域
	 **/
	public static void transformList(List<Region> pre, List<Region> now, List<List<Region>> derivedFromPreList) {
		assert (pre != null);
		assert (now != null);
		assert (derivedFromPreList != null);
		for (List<Region> derivedFromPre : derivedFromPreList) {
			cutDerivedToSubRegion(now, derivedFromPre);
		}
		List<Region> added = new ArrayList<>();
		generateAddedRegion(pre, now, added);
		for (List<Region> derivedFromPre : derivedFromPreList) {
			addRegion(added, derivedFromPre);
		}
	}
	/**
	 * 剪除部分derived, 使得derived成为now的子树
	 */
	private static void cutDerivedToSubRegion(List<Region> now, List<Region> derived) {
		if (now.isEmpty()) {
			derived.clear();
			return;
		} else if (derived.isEmpty()) {
			return;
		}
		Collections.sort(now);
		Collections.sort(derived);
		int nowIdx = 0;
		int derivedIdx = 0;
		while (nowIdx < now.size()) {
			long nowId = now.get(nowIdx).getId();
			while (derivedIdx < derived.size()) {
				long derivedId = derived.get(derivedIdx).getId();
				if (nowId < derivedId) { // 没有找到nowId
					++nowIdx;
					break; // 退出内层循环
				} else if (nowId > derivedId) { // 没有找到derivedId, 被删除了
					derived.remove(derivedIdx);
					continue; // 继续内层循环
				} else { // 找到了, 递归查找
					List<Region> nowSub = now.get(nowIdx).getSub();
					List<Region> derivedSub = derived.get(derivedIdx).getSub();
					if (!Region.isListEmpty(nowSub) && !Region.isListEmpty(derivedSub)) {
						cutDerivedToSubRegion(nowSub, derivedSub);
						if (Region.isListEmpty(derivedSub))
							derived.get(derivedIdx).setSub(null);
					} else if (!Region.isListEmpty(nowSub) && Region.isListEmpty(derivedSub)) { // 截短
					} else if (Region.isListEmpty(nowSub) && !Region.isListEmpty(derivedSub)) { // 变长
						derived.get(derivedIdx).setSub(null);
					}
					++nowIdx;
					++derivedIdx;
					break; // 退出内层循环
				}
			}
			if (derivedIdx >= derived.size())
				break;
		}
		// 删除剩余的
		for (int i = derived.size() - 1; i >= derivedIdx; --i)
			derived.remove(i);
	}
	/**
	 * pre变为now, 计算出增加的区域
	 */
	private static boolean generateAddedRegion(List<Region> pre, List<Region> now, List<Region> added) {
		Collections.sort(pre);
		Collections.sort(now);
		if (pre.isEmpty()) {
			added.addAll(now);
			return true;
		} else if (now.isEmpty()) {
			return false;
		}
		boolean addFlag = false;
		int preIdx = 0;
		int nowIdx = 0;
		while (preIdx < pre.size()) {
			long preId = pre.get(preIdx).getId();
			while (nowIdx < now.size()) {
				long nowId = now.get(nowIdx).getId();
				if (preId < nowId) { // 没有找到preId, 被删除了
					++preIdx;
					break; // 退出内层循环
				} else if (preId > nowId) { // nowId没有找到, 是新加入的
					added.add(now.get(nowIdx));
					addFlag = true;
					++nowIdx;
				} else { // 找到了, 递归查找
					List<Region> preSub = pre.get(preIdx).getSub();
					List<Region> nowSub = now.get(nowIdx).getSub();
					if (!Region.isListEmpty(preSub) && !Region.isListEmpty(nowSub)) {
						List<Region> addedSub = new ArrayList<>();
						boolean childAddFlag = generateAddedRegion(preSub, nowSub, addedSub);
						if (childAddFlag) {
							Region addedNode = new Region(preId, addedSub);
							added.add(addedNode);
							addFlag = true;
						}
					} else if (!Region.isListEmpty(preSub) && Region.isListEmpty(nowSub)) { // 截短
					} else if (Region.isListEmpty(preSub) && !Region.isListEmpty(nowSub)) { // 变长
						added.add(now.get(nowIdx));
						addFlag = true;
					}
					++preIdx;
					++nowIdx;
					break; // 退出内层循环
				}
			}
			if (nowIdx >= now.size())
				break;
		}
		// 添加剩余的
		for (; nowIdx < now.size(); ++nowIdx) {
			added.add(now.get(nowIdx));
			addFlag = true;
		}
		return addFlag;
	}
	/**
	 * 将added的区域添加到derived
	 */
	public static void addRegion(List<Region> added, List<Region> derived) {
		Collections.sort(added);
		Collections.sort(derived);
		if (added.isEmpty()) {
			return;
		}
		List<Region> appendList = new ArrayList<>();
		int addedIdx = 0;
		int derivedIdx = 0;
		while (addedIdx < added.size()) {
			long addedId = added.get(addedIdx).getId();
			if (derivedIdx >= derived.size())
				break;
			while (derivedIdx < derived.size()) {
				long derivedId = derived.get(derivedIdx).getId();
				if (addedId < derivedId) { // 没有找到addedId
					appendList.add(added.get(addedIdx));
					++addedIdx;
					break; // 退出内层循环
				} else if (addedId > derivedId) { // 没有找到derivedId
					++derivedIdx;
				} else { // 找到了, 递归查找
					List<Region> addedSub = added.get(addedIdx).getSub();
					List<Region> derivedSub = derived.get(derivedIdx).getSub();
					if (!Region.isListEmpty(addedSub)) {
						if (!Region.isListEmpty(derivedSub)) {
							addRegion(addedSub, derivedSub);
						} else {
							derived.get(derivedIdx).setSub(addedSub);
						}
					}
					++addedIdx;
					++derivedIdx;
					break; // 退出内层循环
				}
			}
		}
		// 插入剩余的
		for (; addedIdx < added.size(); ++addedIdx) {
			appendList.add(added.get(addedIdx));
		}
		// 全部插入
		derived.addAll(appendList);
		Collections.sort(derived); // 插入影响排序, 重新排序
	}
	private static void testCompressStr() {
		String preCompressStr = "110000(110100(110101,110102,110105,110117),110200(110228,110229))";
		String nowCompressStr = "110000(110100(110101,110105,110106,110117)),220000(220100(220117))";
		String derCompressStr = "110000(110100(110101,110102,110105,110117),110200(110229))";
		List<Region> pre = Region.buildFromCompressStr(preCompressStr);
		List<Region> now = Region.buildFromCompressStr(nowCompressStr);
		List<Region> der = Region.buildFromCompressStr(derCompressStr);
		transformOne(pre, now, der);
		Region.printAsCompressStr(der);
	}
	public static void main(String[] argv) {
		testCompressStr();
	}
}
